package com.lucien.Sort;

import java.util.Arrays;

/**
 * @Author cxy
 * @Date 2021/3/2 21:55
 * @Version 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        //将数组进行升序排序
        int [] arr = {10, 4, 6, 8, 5, 9};
        heapSort(arr);
    }

    //堆排序的方法
    public static void heapSort(int [] arr){
        int temp = 0;

        //将无序数组构建成一个堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }

        System.out.println(Arrays.toString(arr));

    }

    /**
     *
     *
     * @param arr       待调整的数组
     * @param i         非叶子节点在数组中的索引
     * @param length    对多少个元素继续调整，逐渐减少
     * 将一个数组(二叉树)，调整为大顶堆
     */
    public static void adjustHeap(int [] arr, int i, int length){
        int temp = arr[i];//取出当前元素保存在临时变量
        //j = i * 2 + 1 | j是i的左子节点
        for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
            if (j+1 < length && arr[j] < arr[j+1]) {//左子节点的值小于右子节点的值
                j++; // j 指向右子节点
            }
            if (arr[j] > temp) {//如果子节点大于父节点
                arr[i] = arr[j];//将较大的值赋给当前节点
                i = j;          //i 指向 j 继续循环比较
            }else {
                break;
            }
            //for结束后，已经将以 i 为父节点的数的最大值 放在了最顶（局部）
            arr[i] = temp;//将temp的值放到调整后的位置
        }



    }

}
